/*
	35. 搜索插入位置
	给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
	如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

	请必须使用时间复杂度为 O(log n) 的算法。
*/

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
		
        int l = 0, r = nums.size() - 1;
		
		// 数组中只有一个元素且为 target 的情况
        if(r == 0 && target == nums[0]) return 0;
		
        while(l<r){
             int mid = l + r >> 1;
             if(target == nums[mid]) return mid;
			 
			 // 此处性质为 target < nums[mid]
             if(target < nums[mid]) r = mid;
             else l = mid + 1;
        }
		
		// 此处包含 target 为最后一个元素和 target 找不到的情况
		// 当 target 为最后一个元素, 上面的循环必然会到 l == r, 则 return l;
		// 若不存在, 则最后的要插入的位置一定在 l 下标的附近
		// 通过观察, 当 target > nums[l] 时, 要插入的位置为 l+1 ; 当 target < nums[l] 时, 要插入的位置为 l.
        if(target > nums[l]) return l + 1;
        return l;
    }
};
